package leetcode.editor.cn.dsa11_sort;
// 给你两个数组，arr1 和 arr2，
// arr2 中的元素各不相同
// arr2 中的每个元素都出现在 arr1 中 
// 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末
//尾。 
//
// 示例： 
// 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
// 输出：[2,2,2,1,4,3,3,9,6,7,19]
// 
// 提示：
// 1 <= arr1.length, arr2.length <= 1000
// 0 <= arr1[i], arr2[i] <= 1000 
// arr2 中的元素 arr2[i] 各不相同 
// arr2 中的每个元素 arr2[i] 都出现在 arr1 中 
// 
// Related Topics 排序 数组 
// 👍 147 👎 0

import java.util.Arrays;

public class RelativeSortArray1122 {
    public static void main(String[] args) {
        Solution solution = new RelativeSortArray1122().new Solution();
        int[] arr1 = {2,3,1,3,2,4,6,7,9,2,19};
        int[] arr2 = {2,1,4,3,9,6};
        solution.relativeSortArray(arr1, arr2);
        System.out.println(Arrays.toString(arr1));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 思路：
         * 1.定义哈希表，以数组2元素的值为索引，存储元素的个数，默认为1
         * 2.遍历数组1，根据哈希表进行查找，能查找到的元素个数+1，否则存入新数组
         * 3.对新数组中元素进行升序排序
         * 4.遍历数组2，根据哈希表中元素出现的个数，对数组1进行重新赋值
         * 5.将排序好的新数组按照升序放在数组1的末尾
         * @param arr1
         * @param arr2
         * @return
         */
        public int[] relativeSortArray(int[] arr1, int[] arr2) {
            // 1.定义哈希表，以数组2元素的值为索引，存储元素的个数
            int[] hash = new int[1001]; // 元素值范围从0-1000
            for (int i = 0; i < arr2.length; i++) {
                hash[arr2[i]] = 1; // 默认为1
            }
            int[] other = new int[arr1.length - arr2.length];
            int index = 0;
            // 2.遍历数组1，根据哈希表进行查找，能查找到的元素个数+1，否则存入新数组
            for (int i = 0; i < arr1.length; i++) {
                int count = hash[arr1[i]];
                if (count == 0) {
                    other[index++] = arr1[i];
                } else {
                    hash[arr1[i]] = ++count;
                }
            }
            // 3.对新数组中元素进行升序排序(使用快速排序)
            if (index >= 2) quickSort(other, 0, index - 1);
            int k = 0;
            // 4.遍历数组2，根据哈希表中元素出现的个数，对数组1进行重新赋值
            for (int i = 0; i < arr2.length; i++) {
                int c = hash[arr2[i]];
                if (c != 0) {
                    for (int j = 0; j < c - 1; j++) {
                        arr1[k++] = arr2[i];
                    }
                }
            }
            // 5.将排序好的新数组按照升序放在数组1的末尾
            for (int i = 0; i < index; i++) {
                arr1[k++] = other[i];
            }
            return arr1;
        }
        // 快速排序
        public void quickSort(int[] arr, int low, int high) {
            int i = low, j = high;
            int temp = arr[i];
            while (i < j) {
                while (i < j && arr[j] >= temp) j--;
                if (i < j) arr[i++] = arr[j];
                while (i < j && arr[i] <= temp) i++;
                if (i < j) arr[j--] = arr[i];
            }
            arr[i] = temp;
            if (low < i - 1) quickSort(arr, low, i - 1);
            if (high > i + 1) quickSort(arr, i + 1, high);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}